/*
 * @lc app=leetcode.cn id=927 lang=typescript
 *
 * [927] 三等分
 */

// @lc code=start
function threeEqualParts(arr: number[]): number[] {
  const sum = arr.reduce((pre, cur) => pre + cur);
  if (sum % 3 !== 0) return [-1, -1];
  if (sum === 0) return [0, 2];

  const part = sum / 3;
  const n = arr.length;
  // 第一区间的开始位置
  let p1 = 0;
  // 第二区间的开始位置
  let p2 = 0;
  // 第三区间的开始位置
  let p3 = 0;
  let cur = 0;
  for (let i = 0; i < n; i++) {
    if (arr[i] === 1) {
      if (cur === 0) {
        p1 = i;
      } else if (cur === part) {
        p2 = i;
      } else if (cur === 2 * part) {
        p3 = i;
      }
      cur++;
    }
  }

  // 二进制串的长度
  let size = n - p3;
  if (p1 + size <= p2 && p2 + size <= p3) {
    let i = 0;
    while (p3 + i < n) {
      if (arr[p1 + i] !== arr[p3 + i] || arr[p2 + i] !== arr[p3 + i]) {
        return [-1, -1];
      }
      i++;
    }
    return [p1 + size - 1, p2 + size];
  }

  return [-1, -1];
}
// @lc code=end
